package com.czm.test;

import javax.sound.midi.Soundbank;
import java.util.*;
import java.util.stream.Collectors;

/**
 * @author CZM
 * @date 2022 06 26 10:33
 */
public class Day03 {
    public static void main(String[] args) {
//        test037();
//        test036();
//        test036_2();
//        test035();
//        test034();
//        test033();
//        test032();
//        test031();
//        test030();

        // HashMap是按照key升序排序
//        Map<Integer, Integer> map = new HashMap<>();
//        map.put(1,11 );
//        map.put(5,5 );
//        map.put(4,4 );
//        map.put(2,20 );
//        map.put(3,3 );
//        for (Integer m :map.keySet()){
//            if (m == 4) {
//                System.out.println("-----");
//            }
//            System.out.println(m + " " + map.get(m));
//        }
    }

    /**
     * 一个工厂有m条流水线
     * 来并行完成n个独立的作业
     * 该工厂设置了一个调度系统
     * 在安排作业时，总是优先执行处理时间最短的作业
     * 现给定流水线个数m
     * 需要完成的作业数n
     * 每个作业的处理时间分别为 t1,t2...tn
     * 请你编程计算处理完所有作业的耗时为多少
     * 当n>m时 首先处理时间短的m个作业进入流水线
     * 其他的等待
     * 当某个作业完成时，
     * 依次从剩余作业中取处理时间最短的
     * 进入处理
     * <p>
     * 输入描述：
     * 第一行为两个整数(采取空格分隔)
     * 分别表示流水线个数m和作业数n
     * 第二行输入n个整数(采取空格分隔)
     * 表示每个作业的处理时长 t1,t2...tn
     * 0<m,n<100
     * 0<t1,t2...tn<100
     * <p>
     * 输出描述
     * 输出处理完所有作业的总时长
     * <p>
     * 案例
     * 输入
     * 3 5
     * 8 4 3 2 10
     * 输出
     * 13
     * 说明
     * 先安排时间为2,3,4的三个作业
     * 第一条流水线先完成作业
     * 调度剩余时间最短的作业8
     * 第二条流水线完成作业
     * 调度剩余时间最短的作业10
     * 总共耗时 就是二条流水线完成作业时间13(3+10)
     * <p>
     * 3 9
     * 1 1 1 2 3 4 6 7 8
     */
    // 与第58题一样，以下是思路
    public static void test037() {
        int sum = 0;
        int res = 0;
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(1);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(6);
        list.add(7);
        list.add(8);
        for (int i = 0; i < 3; i++) {
            for (int j = i; j < 9; j += 3) {
                sum += list.get(j);
            }
            res = Math.max(res, sum);
            sum = 0;
        }
        System.out.println(res);
    }

    /**
     * 用数组代表每个人的能力
     * 一个比赛活动要求 参赛团队的最低能力值为N
     * 每个团队可以由一人或者两人组成
     * 且一个人只能参加一个团队
     * 计算出最多可以派出多少只符合要求的队伍
     * <p>
     * 输入描述
     * 5
     * 3 1 5 7 9
     * 8
     * 第一行代表总人数，范围  1~500000
     * 第二行数组代表每个人的能力
     * 数组大小范围 1~500000
     * 元素取值范围 1~500000
     * 第三行数值为团队要求的最低能力值
     * 1~500000
     * <p>
     * 输出描述
     * 3
     * 最多可以派出的团队数量
     * <p>
     * 示例一
     * 输入
     * 5
     * 3 1 5 7 9
     * 8
     * <p>
     * 输出
     * 3
     * <p>
     * 说明 3、5组成一队   1、7一队  9自己一队  输出3
     * <p>
     * 7
     * 3 1 5 7 9 2 6
     * 8
     * 输出
     * 4
     * <p>
     * 3
     * 1 1 9
     * 8
     * 输出
     * 1
     */
    public static void test036() {
        Scanner sc = new Scanner(System.in);
        int len = Integer.parseInt(sc.nextLine());
        String[] split = sc.nextLine().split(" ");
        int requireValue = Integer.parseInt(sc.nextLine());
        List<Integer> list = new ArrayList<>();
        int count = 0;
        for (int i = 0; i < len; i++) {
            int num = Integer.parseInt(split[i]);
            if (num >= requireValue) {
                count++;
            } else {
                list.add(num);
            }
        }
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(i) + list.get(j) >= requireValue) {
                    count++;
                    list.remove(j);
                    list.remove(i);
                    i--;
                }
            }
        }
        System.out.println(count);
    }

    // 双指针
    public static void test036_2() {
        Scanner sc = new Scanner(System.in);
        int len = Integer.parseInt(sc.nextLine());
        String[] split = sc.nextLine().split(" ");
        int requireValue = Integer.parseInt(sc.nextLine());
        List<Integer> list = new ArrayList<>();
        int count = 0;
        for (int i = 0; i < len; i++) {
            int num = Integer.parseInt(split[i]);
            if (num >= requireValue) {
                count++;
            } else {
                list.add(num);
            }
        }
        Collections.sort(list);
        int start = 0;
        int end = list.size() - 1;
        while (start < end) {
            if (list.get(start) + list.get(end) >= requireValue) {
                count++;
                start++;
                end--;
            } else {
                start++;
            }
        }
        System.out.println(count);
    }

    /**
     * 同一个数轴x有两个点的集合A={A1,A2,...,Am}和B={B1,B2,...,Bm}
     * A(i)和B(j)均为正整数
     * A、B已经按照从小到大排好序，AB均不为空
     * 给定一个距离R 正整数，列出同时满足如下条件的
     * (A(i),B(j))数对
     * 1. A(i)<=B(j)
     * 2. A(i),B(j)之间距离小于等于R
     * 3. 在满足1，2的情况下每个A(i)只需输出距离最近的B(j)
     * 4. 输出结果按A(i)从小到大排序
     * <p>
     * 输入描述
     * 第一行三个正整数m n R
     * 第二行m个正整数 表示集合A
     * 第三行n个正整数 表示集合B
     * <p>
     * 输入限制 1<=R<=100000
     * 1<=n,m<=100000
     * 1<= A(i),B(j) <= 1000000000
     * <p>
     * 输出描述
     * 每组数对输出一行 A(i)和B(j)
     * 以空格隔开
     * <p>
     * 示例一
     * 输入
     * 4 5 5
     * 1 5 5 10
     * 1 3 8 8 20
     * <p>
     * 输出
     * 1 1
     * 5 8
     * 5 8
     */
    public static void test035() {
        Scanner sc = new Scanner(System.in);
        String[] split = sc.nextLine().split(" ");
        String[] a = sc.nextLine().split(" ");
        String[] b = sc.nextLine().split(" ");
        int aLen = Integer.parseInt(split[0]);
        int bLen = Integer.parseInt(split[1]);
        int r = Integer.parseInt(split[2]);
        for (int i = 0; i < aLen; i++) {
            for (int j = 0; j < bLen; j++) {
                int numI = Integer.parseInt(a[i]);
                int numJ = Integer.parseInt(b[j]);
                if (numI <= numJ && (numJ - numI <= r)) {
                    System.out.println(numI + " " + numJ);
                    break;
                }
            }
        }

    }

    /**
     * 1.众数是指一组数据中出现次数多的数
     * 众数可以是多个
     * 2.中位数是指把一组数据从小到大排列，最中间的那个数，
     * 如果这组数据的个数是奇数，那最中间那个就是中位数
     * 如果这组数据的个数为偶数，那就把中间的两个数之和除以2就是中位数
     * 3.查找整型数组中元素的众数并组成一个新的数组
     * 求新数组的中位数
     * <p>
     * 输入描述
     * 输入一个一维整型数组，数组大小取值范围   0<n<1000
     * 数组中每个元素取值范围，  0<e<1000
     * <p>
     * 输出描述
     * 输出众数组成的新数组的中位数
     * <p>
     * 示例一
     * 输入：
     * 10 11 21 19 21 17 21 16 21 18 16
     * 输出
     * 21
     * <p>
     * 示例二
     * 输入
     * 2 1 5 4 3 3 9 2 7 4 6 2 15 4 2 4
     * 输出
     * 3
     * <p>
     * 示例三
     * 输入
     * 5 1 5 3 5 2 5 5 7 6 7 3 7 11 7 55 7 9 98 9 17 9 15 9 9 1 39
     * 输出
     * 7
     */
    public static void test034() {
        Scanner sc = new Scanner(System.in);
        String[] split = sc.nextLine().split(" ");
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < split.length; i++) {
            int num = Integer.parseInt(split[i]);
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        int count = 0;
        for (Integer m : map.keySet()) {
            count = Math.max(count, map.get(m));
        }

        List<Integer> list = new ArrayList<>();
        for (Integer m : map.keySet()) {
            if (map.get(m) >= count) {
                list.add(m);
            }
        }
        Collections.sort(list);
        int size = list.size();
        if (size % 2 == 0) {
            System.out.println((list.get(size / 2 - 1) + list.get(size / 2)) / 2);
        } else {
            System.out.println(list.get(size / 2));
        }

    }

    /**
     * 有一个简易内存池，内存按照大小粒度分类
     * 每个粒度有若干个可用内存资源
     * 用户会进行一系列内存申请
     * 需要按需分配内存池中的资源
     * 返回申请结果成功失败列表
     * 分配规则如下
     * 1.分配的内存要大于等于内存的申请量
     * 存在满足需求的内存就必须分配
     * 优先分配粒度小的，但内存不能拆分使用
     * 2.需要按申请顺序分配
     * 先申请的先分配，有可用内存分配则申请结果为true
     * 没有可用则返回false
     * 注释：不考虑内存释放
     * <p>
     * 输入描述
     * 输入为两行字符串
     * 第一行为内存池资源列表
     * 包含内存粒度数据信息，粒度数据间用逗号分割
     * 一个粒度信息内用冒号分割
     * 冒号前为内存粒度大小，冒号后为数量
     * 资源列表不大于1024
     * 每个粒度的数量不大于4096
     * <p>
     * 第二行为申请列表
     * 申请的内存大小间用逗号分割，申请列表不大于100000
     * <p>
     * 如
     * 64:2,128:1,32:4,1:128
     * 50,36,64,128,127
     * <p>
     * 输出描述
     * 输出为内存池分配结果
     * 如true,true,true,false,false
     * <p>
     * 示例一：
     * 输入：
     * 64:2,128:1,32:4,1:128
     * 50,36,64,128,127
     * 输出：
     * true,true,true,false,false
     * <p>
     * 说明:
     * 内存池资源包含：64k共2个、128k共1个、32k共4个、1k共128个的内存资源
     * 针对50,36,64,128,127的内存申请序列，
     * 分配的内存依次是，64,64,128,null,null
     * 第三次申请内存时已经将128分配出去，因此输出的结果是
     * true,true,true,false,false
     */
    public static void test033() {
        Scanner sc = new Scanner(System.in);
        String[] split1 = sc.nextLine().split(",");
        String[] split2 = sc.nextLine().split(",");
        // treeMap是有序的，按照key降序排序，hashMap是无序的
        Map<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < split1.length; i++) {
            String[] split = split1[i].split(":");
            int num = Integer.parseInt(split[0]);
            int count = Integer.parseInt(split[1]);
            map.put(num, count);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < split2.length; i++) {
            boolean flag = true;
            for (Integer m : map.keySet()) {
                int key = Integer.parseInt(split2[i]);
                if (m > key && map.get(m) >= 1) {
                    sb.append("true,");
                    map.put(m, map.get(m) - 1);
                    flag = false;
                    break;
                }
            }
            if (flag) {
                sb.append("false,");
            }
        }
        System.out.println(sb.toString().substring(0, sb.length() - 1));
    }

    /**
     * 有一个N个整数的数组
     * 和一个长度为M的窗口
     * 窗口从数组内的第一个数开始滑动
     * 直到窗口不能滑动为止
     * 每次滑动产生一个窗口  和窗口内所有数的和
     * 求窗口滑动产生的所有窗口和的最大值
     * <p>
     * 输入描述
     * 第一行输入一个正整数N
     * 表示整数个数  0<N<100000
     * 第二行输入N个整数
     * 整数取值范围   [-100,100]
     * 第三行输入正整数M
     * M代表窗口的大小
     * M<=100000 并<=N
     * <p>
     * 输出描述
     * 窗口滑动产生所有窗口和的最大值
     * <p>
     * 示例一
     * 输入
     * 6
     * 12 10 20 30 15 23
     * 3
     * <p>
     * 输出
     * 68
     */
    public static void test032() {
        Scanner sc = new Scanner(System.in);
        int len = Integer.parseInt(sc.nextLine());
        String[] split = sc.nextLine().split(" ");
        int num = Integer.parseInt(sc.nextLine());
        int res = 0;
        for (int i = 0; i <= len - num; i++) {
            int sum = 0;
            for (int j = 0; j < num; j++) {
                sum = sum + Integer.parseInt(split[i + j]);
            }
            res = Math.max(res, sum);
        }
        System.out.println(res);
    }

    /**
     * 一个整数可以由连续的自然数之和来表示
     * 给定一个整数
     * 计算该整数有几种连续自然数之和的表达式
     * 并打印出每一种表达式
     * <p>
     * 输入描述
     * 一个目标整数t  1<= t <=1000
     * <p>
     * 输出描述
     * 1.该整数的所有表达式和表达式的个数
     * 如果有多种表达式，自然数个数最少的表达式优先输出
     * 2.每个表达式中按自然数递增输出
     * <p>
     * 具体的格式参见样例
     * 在每个测试数据结束时，输出一行"Result:X"
     * 其中X是最终的表达式个数
     * <p>
     * 输入
     * 9
     * <p>
     * 输出
     * 9=9
     * 9=4+5
     * 9=2+3+4
     * Result:3
     * <p>
     * 说明 整数9有三种表达方法：
     * <p>
     * 示例二
     * 输入
     * 10
     * 输出
     * 10=10
     * 10=1+2+3+4
     * Result:2
     */
    public static void test031() {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        System.out.println(num + "=" + num);
        List<String> list = new ArrayList<>();
        for (int i = 1; i <= num / 2; i++) {
            int sum = 0;
            StringBuilder sb = new StringBuilder();
            for (int j = i; j <= num; j++) {
                sum += j;
                sb = sb.append(j).append("+");
                if (sum == num) {
                    list.add(num + "=" + sb.substring(0, sb.length() - 1));
                    break;
                } else if (sum > num) {
                    break;
                }
            }
        }
        for (int i = list.size() - 1; i >= 0; i--) {
            System.out.println(list.get(i));
        }
        System.out.println("Result:" + (list.size() + 1));
    }

    /**
     * 给定一个仅包含0和1的n*n二维矩阵
     * 请计算二维矩阵的最大值
     * 计算规则如下
     * 1、每行元素按下标顺序组成一个二进制数(下标越大约排在低位)，
     * 二进制数的值就是该行的值，矩阵各行之和为矩阵的值
     * 2、允许通过向左或向右整体循环移动每个元素来改变元素在行中的位置
     * 比如
     * [1,0,1,1,1]   向右整体循环移动两位  [1,1,1,0,1]
     * 二进制数为11101 值为29
     * [1,0,1,1,1]   向左整体循环移动两位  [1,1,1,1,0]
     * 二进制数为11110 值为30
     * <p>
     * 输入描述
     * 1.数据的第一行为正整数，记录了N的大小
     * 0<N<=20
     * 2.输入的第2到n+1行为二维矩阵信息
     * 行内元素边角逗号分割
     * <p>
     * 输出描述
     * 矩阵的最大值
     * <p>
     * 示例1
     * <p>
     * 输入
     * 5
     * 1,0,0,0,1   24
     * 0,0,0,1,1   24
     * 0,1,0,1,0   20
     * 1,0,0,1,1   28
     * 1,0,1,0,1   26
     * <p>
     * 输出
     * 122
     * <p>
     * 说明第一行向右整体循环移动一位，得到最大值  11000  24
     * <p>
     * 因此最大122
     */
    public static void test030() {
        Scanner sc = new Scanner(System.in);
        int num = Integer.parseInt(sc.nextLine());
        List<String> list = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            list.add(sc.nextLine());
        }
        int res = 0;
        for (int i = 0; i < list.size(); i++) {
            String str = list.get(i).replaceAll(",", "");
            int sum = 0;
            for (int j = 0; j < num; j++) {
                sum = Math.max(sum, Integer.parseInt(str, 2));
                str = str.substring(num - 1) + str.substring(0, num - 1);
            }
            res += sum;
        }
        System.out.println(res);
    }

}

